1. Field of the Invention
The present invention is related to the field of data structures stored in a memory of a computer system. More specifically, the present invention is related to a method for obtaining a seed value to be used as input to a hashing algorithm, the hashing algorithm providing a key for efficiently and quickly accessing records of a table in a memory of a computer system.
2. Description of the Related Art
There are numerous well known methods for searching for data in a data structure stored in a memory of a computer system to find a particular item of information. Certainly, it is appropriate to implement methods for organizing and searching for data in the data structure in a way that reduces the amount of memory required to store the data and perform the search in a more efficient manner. Before discussing such methods and the present invention, a brief mention of terms commonly used in the description of data structures and search techniques performed thereon is in order.
A table, or a file, comprises a group of data elements, each of which may be called an entry, or a record, in the table. Generally, an index value is associated with each record. The index value is used to identify the different records. The index value associated with a particular record may or may not need to be unique, depending on the search method utilized in accessing the table. Furthermore, the index value may be embedded within the record itself, or otherwise associated with the record.
A search method accepts one or more keys as input and attempts to locate a record within a table stored in the memory of a computer system whose associated index value matches the key. The search method may return the contents of the record, or a pointer to the record. The contents of the record may be data, program code, or a pointer to either data or program code, for example. If the search of a table is unsuccessful in finding the index value, then there is no record in the table associated with the index value. Typically, if the search is unsuccessful, a new record is added to the table with the key as its index value.
A table is stored in a data structure in the memory or an external storage, e.g., magnetic disk, of a computer system. The form of the data structure may be an array of records, a tree, a linked list, etc. Certain search methods are generally more applicable to one form and location of a data structure than another. Thus, the type and location of the data structure in which a table is stored is compatible with the search method used to access information within the table. For example, the present invention is related to search operations on a file or table that is organized as an array or group of arrays in a memory of an information handling device.
The efficiency and speed with which an algorithm searches for and identifies a record in a table is, understandably, a very important consideration in many fields of data computing. In particular, often utilized lookup routines benefit from and commonly rely on sophisticated techniques and schemes for accessing information in a data structure, particularly when accessing large databases of information. For example, optimized lookup routines are used in data communication networks to identify data packets, identify the destination for such data packets, and determine whether a data packet forwarding device should receive, forward, or filter such data packets. As data communication networks become larger and handle greater amounts of data traffic, the ability of data packet forwarding devices such as a bridge, switch, or router, or the like, to quickly identify addresses in data packets for purposes of determining whether and where to forward such data packets is paramount. To that end, what is needed is an improved method for searching for a record in a table, for example, searching for an entry in a forwarding database, indexed by a destination address, that indicates the port of a data packet forwarding device out of which data packets having the destination address should be forwarded by the data packet forwarding device. In particular, what is needed is a hashing algorithm in which the seed values input to the hashing algorithm are selected to achieve the best results in terms of reducing collisions and/or rehashing to find the desired record.